//
// Created by weslywang on 2020/4/25.
//
#include "../common/common.h"

void pathSumCalc(TreeNode *root, int sum, vector<int> *preList, vector<vector<int>> *result) {
    if (!root) {
        return;
    }
    preList->push_back(root->val);
    if (sum == root->val && !root->right && !root->left) {
        vector<int> preListBack(*preList);
        result->push_back(preListBack);
    } else {
        pathSumCalc(root->left, sum - root->val, preList, result);
        pathSumCalc(root->right, sum - root->val, preList, result);
    }
    preList->pop_back();
}

vector<vector<int>> pathSum(TreeNode *root, int sum) {
    vector<vector<int>> result;
    vector<int> tmp;
    pathSumCalc(root, sum, &tmp, &result);
    return result;
}

int main() {
    Common common;
    int a[] = {1, 2, 3, 4, 5};
    vector<vector<int>> numList = common.loadData();
    for (int i = 0; i < numList.size(); i++) {
        TreeNode *root = common.makeTree(numList[i]);
        common.printTree(root);
        pathSum(root, 22);
        cout << "**************" << endl;
    }
    return 0;
}